As online social networks such as Facebook and MySpace gaining popularity rapidly, social networks have become an ubiquitous part of many people's daily lives. One major topic in social network analysis is the study of communities in social networks. For instance, in Wikipedia, the online social network service is defined as “A social network service focuses on building online communities of people who share interests and activities, or who are interested in exploring the interests and activities of others”. Analyzing communities in a social network, in addition to serving scientific purposes (e.g., in sociology and social psychology), helps improve user experiences (e.g., through friend recommendation services) and provides business values (e.g., in target advertisement and market segmentation analysis).
Communities have long been studied in various social networks. For example, in social science an important research topic is to identify cohesive subgroups of individuals within a social network where cohesive subgroups are defined as “subsets of actors among whom there are relatively strong, direct, intense, frequent, or positive ties”. As another example, communities also play an important role in Web analysis, where a Web community is defined as “a set of sites that have more links to members of the community than to non-members”.
Social networks are usually represented by graphs where nodes represent individuals and edges represent relationships and interactions among individuals. Based on this graph representation, there exists a large body of work on analyzing communities in static social networks, ranging from well-established social network analysis to recent successful applications such as Web community discovery . However, these studies overlooked an important feature of communities—communities in real life are usually dynamic. On a macroscopic level, community structures evolve over time. For example, a political community whose members' main interest is the presidential election may become less active after the election takes place. On a microscopic level, individuals may change their community memberships, due to the shifts of their interests or due to certain external events. In this respect, the above studies that analyze static communities fail to capture the important dynamics in communities.
Recently, there have been a growing body of work on analyzing dynamic communities in social networks. Some of these studies adopted a two-step approach where first static analysis is applied to the snapshots of the social network at different time steps, and then community evolutions are introduced afterwards to interpret the change of communities over time. Because data in real world are often noisy, such a two-step approach often results in unstable community structures and consequentially, unwarranted community evolutions. Some more recent studies attempted to unify the processes of community extraction and evolution extraction by using certain heuristics, such as regularizing temporal smoothness. Although some encouraging results were reported, none of these studies explicitly model the transition or change of community memberships, which is the key to the analysis of dynamic social network. In addition, most existing approaches consider point estimation in their studies, i.e., only estimate the most likely value for the unknown parameters. Given the large scale of social networks and potential noise in data, it is likely that the network data may not be sufficient to determine the exact value of parameters, and therefore it is important to develop methods beyond point estimation in order to model and capture the uncertainty in parameter estimation.
Finding communities is an important research topic in social network analysis. For the task of community discovery, many approaches such as clique-based, degree-based, and matrix-perturbation-based, have been proposed. Wasserman et al. gave a comprehensive survey on these approaches. Community discovery is also related to some important research issues in other fields. For example, in applied physics, communities are important in analyzing modules in a physical system and various algorithms have been proposed to discover modular structures in physical systems. As another example, in the machine learning field, finding communities is closely related to graph-based clustering algorithms, such as the normalized cut algorithm proposed by Shi et al. and the graph-factorization clustering (GFC) algorithm proposed by Yu et al. However, all these approaches focused on analyzing static networks while the focus in this study is on analyzing dynamic social networks.
In the field of statistics, a well-studied probabilistic model is the stochastic block model (SBM). This model had been originally proposed by Holland et al. and have been successfully applied in various areas such as social science and bioinformatics. Researchers have extended the stochastic block model in different directions. For example, Airoldi et al. proposed a mixed-membership stochastic block model, Kemp et al. proposed a model that allows an unbounded number of clusters, and Hofman et al. proposed a Bayesian approach based on the stochastic block model to infer module assignments and to identify the optimal number of modules. The new model is also an extension of the stochastic block model. However, in comparison to the above approaches which focused on static social networks, the approach explicitly models the change of community membership over time and therefore can discovery communities and their evolutions simultaneously in dynamic social networks.
Recently, finding communities and their evolutions in dynamic networks has gained more and more attention. Asur et al. introduced a family of events on both communities and individuals to characterize evolution of communities. Tantipathananandh et al. proposed an optimization-based approach for modeling dynamic community structure. Chi et al. proposed an evolutionary version of the spectral clustering algorithms. They used graph cut as a metric for measuring community structures and community evolutions. Lin et al. extended the graph-factorization clustering (GFC) and proposed the FacetNet algorithm for analyzing dynamic communities.